翻訳と辞書 Words near each other ・ Modular arithmetic ・ Modular art ・ Modular Audio Recognition Framework ・ Modular Body Armor Vest ・ Modular Boot System ・ Modular building ・ Modular Capture Vessel ・ Modular classrooms ・ Modular Common Spacecraft Bus ・ Modular connector ・ Modular constructivism ・ Modular crate electronics ・ Modular curve ・ Modular data center ・ Modular Debugger ・ Modular decomposition ・ Modular design ・ Modular elliptic curve ・ Modular Engine Management System ・ Modular equation ・ Modular Equipment Transporter ・ Modular exponentiation ・ Modular form ・ Modular function deployment ・ Modular group ・ Modular Handgun System ・ Modular Integrated Communications Helmet ・ Modular invariance ・ Modular invariant ・ Modular invariant theory Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Modular decomposition ： ウィキペディア英語版 Modular decomposition In graph theory, the modular decomposition is a decomposition of a graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a proper subset of another. Modules therefore lead to a recursive (hierarchical) decomposition of the graph, instead of just a partition. There are variants of modular decomposition for undirected graphs and directed graphs. For each undirected graph, this decomposition is unique. This notion can be generalized to other structures (for example directed graphs) and is useful to design efficient algorithms for the recognition of some graph classes, for finding transitive orientations of comparability graphs, for optimization problems on graphs, and for graph drawing. == Modules == As the notion of modules has been rediscovered in many areas, ''modules'' have also been called ''autonomous sets'', ''homogeneous sets'', ''intervals'', and ''partitive sets''. Perhaps the earliest reference to them, and the first description of modular quotients and the graph decomposition they give rise to appeared in (Gallai 1967). A ''module'' of a graph is a generalization of a connected component. A connected component has the property that it is a set ''X'' of vertices such that every member of ''X'' is a non-neighbor of every vertex not in ''X''. (It is a union of connected components if and only if it has this property.) More generally, ''X'' is a module if, for each vertex $v\; \backslash not\backslash in\; X$, either every member of ''X'' is a non-neighbor of ''v'' or every member of ''X'' is a neighbor of ''v''. Equivalently, ''X'' is a module if all members of ''X'' have the same set of neighbors among vertices not in ''X''. Contrary to the connected components, the modules of a graph are the same as the modules of its complement, and modules can be "nested": one module can be a proper subset of another. Note that the set ''V'' of vertices of a graph is a module, as are its one-element subsets and the empty set; these are called the trivial modules. A graph may or may not have other modules. A graph is called prime if all of its modules are trivial. Despite these differences, modules preserve a desirable property of connected components, which is that many properties of the subgraph ''G()'' induced by a connected component ''X'' are independent of the rest of the graph. A similar phenomenon also applies to the subgraphs induced by modules. The modules of a graph are therefore of great algorithmic interest. A set of nested modules, of which the modular decomposition is an example, can be used to guide the recursive solution of many combinatorial problems on graphs, such as recognizing and transitively orienting comparability graphs, recognizing and finding permutation representations of permutation graphs, recognizing whether a graph is a cograph and finding a certificate of the answer to the question, recognizing interval graphs and finding interval representations for them, defining distance-hereditary graphs (Spinrad, 2003) and for graph drawing (Papadoupoulos, 2006). They play an important role in Lovász's celebrated proof of the perfect graph theorem (Golumbic, 1980). For recognizing distance-hereditary graphs and circle graphs, a further generalization of modular decomposition, called the split decomposition, is especially useful (Spinrad, 2003). To avoid the possibility of ambiguity in the above definitions, we give the following formal definitions of modules. $G\; =\; (V,E)$. $M\; \backslash subseteq\; V$ is a module of $G$ if: * the vertices of $M$ cannot be distinguished by any vertex in $V\; \backslash backslash\; M$, i.e. $\backslash forall\; u,v\; \backslash in\; M,\; \backslash forall\; x\backslash in\; V\; \backslash backslash\; M$, either $x$ is adjacent to both $u$ and $v$ or $x$ is not adjacent to both $u$ and $v$. * the vertices of $M$ have the same set of outer neighbors, i.e. $\backslash forall\; u,v\; \backslash in\; M,\; N(u)\; \backslash setminus\; M\; =\; N(v)\; \backslash setminus\; M$. $\backslash emptyset$, $V$ and all the singletons $\backslash$ for $v\; \backslash in\; V$ are modules, and are called trivial modules. A graph is prime if all its modules are trivial. Connected components of a graph $G$, or of its complement graph are also modules of $G$. $M$ is a strong module of a graph $G$ if it does not overlap any other module of $G$: $\backslash forall\; M\text{'}$ module of $G$, either $M\; \backslash cap\; M\text{'}\; =\; \backslash emptyset$ or $M\; \backslash subseteq\; M\text{'}$ or $M\text{'}\; \backslash subseteq\; M$. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Modular decomposition」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.